package org.wiming.util;

import com.google.common.collect.Lists;
import lombok.experimental.UtilityClass;
import org.wiming.TreeNode;

import java.util.*;

/**
 * @author : wenchao.long
 * @date : Created in 2021/01/26 9:12 周二
 * @description :
 */
@UtilityClass
public class TreeNodeUtil {

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = Lists.newArrayList();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> deque = new LinkedList<TreeNode>() {{
            push(root);
        }};
        while (!deque.isEmpty()) {
            TreeNode node = deque.pop();
            res.add(node.val);
            if (node.right != null) {
                deque.push(node.right);
            }
            if (node.left != null) {
                deque.push(node.left);
            }
        }
        return res;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = Lists.newLinkedList();
        if (root == null) {
            return res;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.push(root);
        while (!deque.isEmpty()) {
            TreeNode node = deque.pop();
            res.push(node.val);
            if (node.left != null) {
                deque.push(node.left);
            }
            if (node.right != null) {
                deque.push(node.right);
            }
        }
        return res;
    }

    /**
     * 树的深度
     * 从上到下遍历
     *
     * @param root 二叉树
     * @return depth
     */
    public int treeNodeDepthFromTop(TreeNode root) {
        return maxDepth(root, 0, 1);
    }

    private int maxDepth(TreeNode root, int depth, int len) {
        if (root == null) {
            return depth;
        }
        if (root.left == null && root.right == null) {
            depth = Math.max(depth, len);
        }
        int depth1 = maxDepth(root.left, depth, len + 1);
        depth = Math.max(depth1, depth);
        int depth2 = maxDepth(root.right, depth, len + 1);
        depth = Math.max(depth2, depth);
        return depth;
    }

    private int k = 0;
    private int value = 0;

    /**
     * 给定一颗二叉搜索树 找出其中第k大的节点
     * 利用的二叉搜索树的性质: 中序遍历是一个递增序列
     * 如果反过来 右中左 则会是一个递减序列 第k大的节点就是第k个值
     * <p>
     * 剑指offer - 54题
     *
     * @param root 二叉搜索树
     * @param k    k
     * @return 节点的值
     */
    public int kthLargest(TreeNode root, int k) {
        TreeNodeUtil.k = k;
        recursion(root);
        return value;
    }

    private void recursion(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先递归右子树
        recursion(root.right);
        // 如果 k == 0 证明已经找到该值
        if (k == 0) {
            return;
        }
        // 如果 --k == 0 证明是要寻找的值
        if (--k == 0) {
            value = root.val;
            return;
        }
        recursion(root.left);
    }

    /**
     * 输入一棵二叉树的根节点，判断该树是不是平衡二叉树
     * 如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树
     * <p>
     * 剑指offer - 55题
     *
     * @return true - 是平衡二叉树 || false - 不是
     */
    public boolean isBalanced(TreeNode root) {
        return recursionBalanced(root) != -1;
    }

    private int recursionBalanced(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 判断左子树是否平衡
        int left = recursionBalanced(root.left);
        if (left == -1) {
            return -1;
        }
        // 判断右子树是否平衡
        int right = recursionBalanced(root.right);
        if (right == -1) {
            return -1;
        }
        // 判断左右子树的深度之差是不是 <= 1 ? 左右子树最大的深度 : -1
        return Math.abs(left - right) <= 1 ? Math.max(left, right) + 1 : -1;
    }

    /**
     * 二叉树的镜像
     *
     * @param root 二叉树
     * @return TreeNode
     */
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode leftNode = mirrorTree(root.right);
        TreeNode rightNode = mirrorTree(root.left);
        root.left = leftNode;
        root.right = rightNode;
        return root;
    }

    /**
     * 二叉树的镜像 用双向队列实现
     *
     * @param root 二叉树
     * @return TreeNode
     */
    public TreeNode mirrorTreeWithDeque(TreeNode root) {
        if (root == null) {
            return null;
        }
        Deque<TreeNode> deque = new LinkedList<TreeNode>() {{
            add(root);
        }};
        while (!deque.isEmpty()) {
            TreeNode node = deque.remove();
            TreeNode left = node.left;
            TreeNode right = node.right;
            if (left != null) {
                deque.add(left);
            }
            if (right != null) {
                deque.add(right);
            }
            node.left = right;
            node.right = left;
        }
        return root;
    }

    /**
     * 二叉树是否对称
     *
     * @param root 二叉树
     * @return true - 对称
     */
    public boolean isSymmetric(TreeNode root) {
        return root == null || isEquals(root.left, root.right);
    }

    private boolean isEquals(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null ^ right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return isEquals(left.left, right.right) && isEquals(left.right, right.left);
    }

    public boolean isSymmetricWithDeque(TreeNode root) {
        if (root == null) {
            return true;
        }
        Deque<TreeNode> deque = new LinkedList<TreeNode>() {{
            add(root.left);
            add(root.right);
        }};
        while (!deque.isEmpty()) {
            TreeNode left = deque.remove();
            TreeNode right = deque.remove();
            if (left == null && right == null) {
                continue;
            }
            if (left == null || right == null || left.val != right.val) {
                return false;
            }
            deque.add(left.left);
            deque.add(right.right);
            deque.add(left.right);
            deque.add(right.left);
        }
        return true;
    }

    private int[] postorder;
    private int index;
    HashMap<Integer, Integer> map = new HashMap<>();

    /**
     * 由中序和后序构建一颗树
     *
     * @param inorder   中序遍历集合
     * @param postorder 后序遍历集合
     * @return 二叉树
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNodeUtil.postorder = postorder;
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        int length = postorder.length - 1;
        index = length;
        return buildTreeHelper(0, length);
    }

    private TreeNode buildTreeHelper(int left, int right) {
        if (left > right) {
            return null;
        }
        int val = postorder[index--];
        TreeNode root = TreeNode.newInstance(val);
        int i = map.get(val);
        root.right = buildTreeHelper(i + 1, right);
        root.left = buildTreeHelper(left, i - 1);
        return root;
    }

    public TreeNode buildTreeWithDeque(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0) {
            return null;
        }
        int n = postorder.length;
        TreeNode root = TreeNode.newInstance(postorder[n - 1]);
        int inorderIndex = n - 1;
        Deque<TreeNode> deque = new LinkedList<TreeNode>() {{
            addFirst(root);
        }};
        int j = 2;
        for (int i = n - j; i >= 0; i--) {
            int postValue = postorder[i];
            TreeNode node = deque.getFirst();
            if (node.val != inorder[inorderIndex]) {
                node.right = TreeNode.newInstance(postValue);
                deque.addFirst(node.right);
            } else {
                while (!deque.isEmpty() && deque.peek().val == inorder[inorderIndex]) {
                    inorderIndex--;
                    node = deque.pop();
                }
                node.left = TreeNode.newInstance(postValue);
                deque.addFirst(node.left);
            }
        }
        return root;
    }

    /**
     * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在
     * 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
     *
     * @param root 二叉树
     * @param sum  总和
     * @return true - 存在
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        sum = sum - root.val;
        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
    }

    /**
     * 没有递归来的快 甚至慢了2ms
     *
     * @param root 二叉树
     * @param sum  总和
     * @return true - 存在
     */
    public boolean hastPathSumWithQueue(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queue = Lists.newLinkedList();
        Queue<Integer> values = Lists.newLinkedList();
        queue.add(root);
        values.add(root.val);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            int value = values.remove();
            if (node.left == null && node.right == null) {
                if (value == sum) {
                    return true;
                }
                continue;
            }
            if (node.left != null) {
                queue.add(node.left);
                values.add(node.left.val + value);
            }
            if (node.right != null) {
                queue.add(node.right);
                values.add(node.right.val + value);
            }
        }
        return false;
    }

}
